Solving the Resource Constrained Project Scheduling Problem Using the Parallel Tabu Search Designed for the CUDA Platform

摘要

In the paper, a parallel Tabu Search algorithm for the Resource ConstrainedProject Scheduling Problem is proposed. To deal with this NP-hard combinatorialproblem many optimizations have been performed. For example, a resourceevaluation algorithm is selected by a heuristic and an effective Tabu List wasdesigned. In addition to that, a capacity-indexed resource evaluation algorithmwas proposed and the GPU (Graphics Processing Unit) version uses a homogeneousmodel to reduce the required communication bandwidth. According to theexperiments, the GPU version outperforms the optimized parallel CPU versionwith respect to the computational time and the quality of solutions. Incomparison with other existing heuristics, the proposed solution often givesbetter quality solutions.